class Solution:
    def __init__(self):
        self.searched_dic = {1: 0}

    def integerReplacement(self, n: int) -> int:
        if n in self.searched_dic:
            return self.searched_dic[n]
        else:
            if n % 2 == 0:
                mid_res = self.integerReplacement(n // 2) + 1
            else:
                mid_res = min(self.integerReplacement(n+1), self.integerReplacement(n-1)) + 1
            self.searched_dic[n] = mid_res
            return mid_res


a = Solution()
print(a.integerReplacement(8))
print(a.integerReplacement(7))
print(a.integerReplacement(100))
